Shortest palindrome

Time: O(N); Space: O(N); hard

Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it.

Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: s = “aacecaaa”

Output: “aaacecaaa”

Example 2:

Input: s = “abcd”

Output: “dcbabcd”

[1]:

class Solution1(object):
    """
    KMP Algorithm
    Time: O(N)
    Space: O(N)
    """
    def shortestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        def getPrefix(pattern):
            prefix = [-1] * len(pattern)
            j = -1
            for i in range(1, len(pattern)):
                while j > -1 and pattern[j+1] != pattern[i]:
                    j = prefix[j]
                if pattern[j+1] == pattern[i]:
                    j += 1
                prefix[i] = j
            return prefix

        if not s:
            return s

        A = s + s[::-1]
        prefix = getPrefix(A)
        i = prefix[-1]
        while i >= len(s):
            i = prefix[i]
        return s[i+1:][::-1] + s

[2]:

sol = Solution1()

s = "aacecaaa"
assert sol.shortestPalindrome(s) == "aaacecaaa"

s = "abcd"
assert sol.shortestPalindrome(s) == "dcbabcd"

[3]:

class Solution2(object):
    """
    Manacher's Algorithm
    Time: O(N)
    Space: O(N)
    """
    def shortestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        def preProcess(s):
            if not s:
                return ['^', '$']
            string = ['^']
            for c in s:
                string +=  ['#', c]
            string += ['#', '$']
            return string

        string = preProcess(s)
        palindrome = [0] * len(string)
        center, right = 0, 0
        for i in range(1, len(string) - 1):
            i_mirror = 2 * center - i
            if right > i:
                palindrome[i] = min(right - i, palindrome[i_mirror])
            else:
                palindrome[i] = 0

            while string[i + 1 + palindrome[i]] == string[i - 1 - palindrome[i]]:
                palindrome[i] += 1

            if i + palindrome[i] > right:
                center, right = i, i + palindrome[i]

        max_len = 0
        for i in range(1, len(string) - 1):
            if i - palindrome[i] == 1:
                max_len = palindrome[i]
        return s[len(s)-1:max_len-1:-1] + s


[4]:

sol = Solution2()

s = "aacecaaa"
assert sol.shortestPalindrome(s) == "aaacecaaa"

s = "abcd"
assert sol.shortestPalindrome(s) == "dcbabcd"